#include <iostream>
#include <algorithm> 
#include <vector>
#include <math.h>
using namespace std;
const int Infty=999;


//外部使用者可以调用以下函数

//void store(int & show_type);
//（1）邻接矩阵，（2）邻接表，（3）以具体情况而定

//void listVertexes();

//void listEdges();



//顶点的名称不定，写成类模板
template<typename VertexName>
class Graph
{
private:
    struct Edge;
    struct Vertex
    {
        VertexName name;//节点名称

        int sub;//下标为sub

        vector<Edge> Adj;//所有以它为起点的边的vector
        
    };
    
    
    struct Edge
    {
        Vertex st;//起点st

        Vertex ed;//终点ed

        double weight=1;//默认1
    };

    int VertexNum=0;//顶点总数

    int EdgeNum=0;//边的总数

    bool hasDirection;//是否有向

    bool hasWeight;//是否有权

    int show_type;//存储方式（1）矩阵，（2）表，（3）随意

    vector<Edge> EdgeTable;//vector形式存储所有边

    vector<Vertex> VertexTable;//以vector形式存储所有节点

    vector<vector<double>> AdjMatrix;//矩阵表示,里面放权重

    vector<vector<Edge>> AdjList;//链表表示,里面放边

public:
    Graph()
    {
        int i,j,k;
        cin >> EdgeNum >> hasDirection >> hasWeight;
        for(i = 0; i < EdgeNum; i++)
        {
            Edge edge;
            if(hasWeight)
            {
                cin>>edge.st.name>>edge.ed.name>>edge.weight;
                EdgeTable.push_back(edge);
            }
            else
            {
                cin>>edge.st.name>>edge.ed.name;
                EdgeTable.push_back(edge);
            }

            //放起点
             for (j = 0; j < VertexNum; j++)
            {
                if(VertexTable[j].name==EdgeTable[i].st.name)
                    break;
            }
            if (j==VertexNum)
            {
                EdgeTable[i].st.sub= VertexNum;
                VertexTable.push_back(EdgeTable[i].st);
                VertexNum++;
            }
            else EdgeTable[i].st=VertexTable[j];

            //放终点
            for (k = 0; k < VertexNum; k++)
            {
                if(VertexTable[k].name==EdgeTable[i].ed.name)
                    break;
            }
            if (k==VertexNum)
            {
                EdgeTable[i].ed.sub = VertexNum;
                VertexTable.push_back(EdgeTable[i].ed);
                VertexNum++;
            }
            else EdgeTable[i].ed=VertexTable[k];
            

            VertexTable[j].Adj.push_back(EdgeTable[i]);
            if(!hasDirection)
              {
                VertexTable[k].Adj.push_back(EdgeTable[i]);
              } 
        }  
    }




    ~Graph()
    {
        // delete[] VertexTable;
        // *VertexTable = NULL;

        // delete[] EdgeTable;
        // *EdgeTable = NULL;


        // for(int i=0;i<VertexNum;i++)
        // {
        //     delete[] AdjMatrix[i];
        //     AdjMatrix[i] = NULL;
        // }
        // delete[] AdjMatrix;
        // AdjMatrix = NULL;
        

        // for(int j=0;j<VertexNum;j++)
        // {
        //     delete[] AdjList[j];
        //     AdjList[j] = NULL;
        // }
        // delete[] AdjList;
        // AdjList = NULL;
        // VertexNum = 0;

    }

    //
    void PrintAdjMatrix()
    {
        //创建一个矩阵
        for(int i = 0 ;i < VertexNum ; i++)
        {
            AdjMatrix.push_back(vector<double>());
            for(int j = 0; j < VertexNum ; j++)
            {
                //首先赋值极大值
                AdjMatrix[i].push_back(Infty);

                //默认自己到自己为0
                if(i==j)
                {
                    AdjMatrix[i][j]=0;
                }
            }
        }


        //插入边
        for(int i = 0; i < EdgeNum; i++)
        {
            AdjMatrix[EdgeTable[i].st.sub][EdgeTable[i].ed.sub]=EdgeTable[i].weight;
            if(!hasDirection)
                AdjMatrix[EdgeTable[i].ed.sub][EdgeTable[i].st.sub]=EdgeTable[i].weight;

        }   
        


        //输出邻接矩阵
        cout << " "<< endl;
        cout << "The following is AdjMatrix " << endl;
        cout << "  ";

        for(int i=0;i<VertexNum;i++)
        {
            cout << VertexTable[i].name << " ";
        }
        cout << endl;

        for(int i=0;i<VertexNum;i++)
        {
            cout << VertexTable[i].name << " ";
            for(int j=0;j<VertexNum;j++)
            {
                cout << AdjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }

   

    void PrintAdjList()
    {
        //由于每个顶点已经知道以它为起点的边Adj
        //直接创建即可
        for(int i = 0; i < VertexNum; i++)
        {
            AdjList.push_back(VertexTable[i].Adj);
        }

        cout << " "<< endl;
        cout << "The following is AdjList " << endl;
        for(int i = 0; i < VertexNum; i++)
        {
            cout << VertexTable[i].name << " -> ";
            for(int j = 0; j < AdjList[i].size() ; j++)
            {
                //以终点和权重的形式输出
                cout << "(" << AdjList[i][j].ed.name << " , "
                << AdjList[i][j].weight<< ")" << " -> ";
            }
            cout << "NULL" << endl;
        }

    }

    //根据不同需要选择输出方式
    void store(int & show_type)
    {
        if (show_type==1)
        {
            PrintAdjMatrix();
        }
            
        if (show_type==2)
        { 
            PrintAdjList();
        }

        if(show_type==3)
        {
            if(EdgeNum > pow(VertexNum,1.5))
            {
                cout << endl;
                cout << "We choose ADJMatrix by the num of edges and vertexes" << endl;
                PrintAdjMatrix();
            }
            else
            {
                cout << endl;
                cout << "We choose ADJList by the num of edges and vertexes" << endl;
                PrintAdjList();
            }
        }
    }



    //列出所有顶点
    void listVertexes()
    {
        cout << " "<< endl;
        cout << "The following is all vertexes in this graph " << endl;
        int i;
        for(i = 0; i < VertexNum-1; i++)
        {
           cout << VertexTable[i].name << " ";
        }
        cout << VertexTable[i].name << endl;
    }



    //列出所有边，以(u,v,w)形式
    void listEdges()
    {
        cout << " "<< endl;
        cout << "The following is all edges in this graph " << endl;
        int i;
        for(i = 0; i < EdgeNum; i++)
        {
            cout << "( " << EdgeTable[i].st.name << " , " << EdgeTable[i].ed.name 
            << " , " << EdgeTable[i].weight << " )"<<endl;
        }
        
    }

};


